package org.example.everyday;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/5/7 9:44
 */
public class Lc433 {
    public static void main(String[] args) {
        Lc433 lc433 = new Lc433();
        /**
         * 输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
         */
        String start = "AACCGGTT", end = "AAACGGTA";
        String[]  bank = new String[] {"AACCGGTA","AACCGCTA","AAACGGTA"};
        int res = lc433.minMutation(start,end,bank);
        System.out.println(res);

    }
    /**
     * 方法描述: 最小基因变化
     * 
     * @param start .
     * @param end .
     * @param bank .
     * @return int
     * @author 安路路
     * @date 2022/5/7  9:46
     */
    public int minMutation(String start, String end, String[] bank) {
        Set<String> cnt = new HashSet<String>();
        Set<String> visited = new HashSet<String>();
        char[] keys = {'A', 'C', 'G', 'T'};
        for(String w : bank){
            cnt.add(w);
        }

        if(start.equals(end)){
            return 0;
        }
        if(!cnt.contains(end)){
            return -1;
        }

        Queue<String> queue = new ArrayDeque<String>();
        queue.offer(start);
        visited.add(start);

        int step = 1;
        while (!queue.isEmpty()){
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                String curr = queue.poll();
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if(keys[k] != curr.charAt(j)){
                            StringBuffer sb = new StringBuffer(curr);
                            sb.setCharAt(j,keys[k]);
                            String next = sb.toString();
                            if(!visited.contains(next) && cnt.contains(next)){
                                if(next.equals(end)){
                                    return step;
                                }
                                queue.offer(next);
                                visited.add(next);
                            }
                        }
                    }
                }
            }
            step++;
        }

        return -1;
    }
}
